package algorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

public class AlgoB {
	public static void main(String[] args) {
		leastCoin(65);
	}

	/**
	 * 青蛙跳台阶 一只青蛙可以跳上1级台阶，可以跳上2级台阶，也可以跳上3级台阶，求青蛙跳上一个n级的台阶有多少中跳法
	 * 
	 * 逆向思维：考虑最后一步：青蛙最后一步可能跳一阶或两阶或三阶 定义f(n)为跳到第n级台阶的跳法数 f(n) = f(n-1)+f(n-2)+f(n-3)
	 * 即跳到第n级台阶的跳法数等于跳到n-1级台阶的跳法数加上跳到第n-2级台阶的跳法数 边界条件：f(0) = 1, f(1) = 1, f(2) = 2,
	 * f(3) = 3
	 * 
	 * @param i 台阶级数
	 * @return 跳法总数
	 */
	public static int jump(int i) {
		if (i == 0 || i == 1) {
			return 1;
		}
		if (i == 2) {
			return 2;
		}
		if (i == 3) {
			return 3;
		}

		return jump(i - 1) + jump(i - 2) + jump(i - 3);
	}

	/**
	 * 逆序对计数 给定一个数组，求这个数组中逆序对的总数。
	 * 逆向思维：给定一个数组，求这个数组中正序对的总数，然后，数组中所有可能的数对总数减去正序对的总数，就得到了逆序对的总数
	 */
	static void reversePairs(String str) {
		int i = 0;
		int asc = 0;
		int desc = 0;
		while (i < str.length() - 1) {
			char c1 = str.charAt(i);
			char c2 = str.charAt(i + 1);
			if (c1 < c2 || c1 == c2) {
				asc++;
			}
			i++;
		}
		desc = str.length() - 1 - asc;
		System.out.println(desc);
	}

	/**
	 * 缺失的数字 一个包含n个整数的数组，其元素范围从0到n-1，有一个数字缺失，找出这个数字。
	 * 逆向思维：计算1~n-1的和，减去数组所有数字的和，就是缺失的数字。
	 * 
	 * @param nums
	 * @return
	 */
	public static int missingNumber(int[] nums) {
		int sum = (nums.length + 1) * nums.length / 2;
		int res = 0;
		for (int i : nums) {
			res += i;
		}
		return sum - res;
	}

	/**
	 * 非重复元素 找出数组中只出现一次的元素，其他元素都出现两次
	 * 逆向思维：使用异或运算，满足交换律和结合律，任何数与自身异或为0，与0异或结果为自身，所有元素异或结果就是只出现一次的元素。
	 * 
	 * @param nums
	 * @return
	 */
	public static int notduplicateNum(int[] nums) {
		int j = 0;
		for (int i : nums) {
			j ^= i;
		}
		return j;
	}

	/**
	 * 两数之和 抽象问题：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
	 * 具象化：将数组中每个元素和它匹配的另一个元素的目标值存储在一个哈希表中，然后遍历数组，查找每个元素对应的目标值是否在哈希表中。
	 * 
	 * @param arr
	 * @param sum
	 */
	public static void twoSum(int[] arr, int sum) {
		// 创建一个哈希表，存储数组元素及其索引
		HashMap<Integer, Integer> map = new HashMap<>();

		// 遍历数组
		for (int i = 0; i < arr.length; i++) {
			int complement = sum - arr[i]; // 计算当前元素的补数

			// 检查补数是否在哈希表中
			if (map.containsKey(complement)) {
				System.out.println("找到一对和为 " + sum + " 的数: " + arr[i] + " 和 " + complement);
				return; // 找到就返回
			}

			// 如果没有找到补数，则将当前元素存入哈希表
			map.put(arr[i], i);
		}

		System.out.println("没有找到符合条件的两数");
	}

	/**
	 * 判断括号是否有效
	 * 
	 * 有效的括号 抽象问题：给定一个只包含（）的字符串，判断字符串是否有效
	 * 具象化：使用栈数据结构，遍历字符串，对于每个开括号，将其放入栈中，对于每个闭括号，弹出栈顶元素并检查是否匹配
	 *
	 * @param brackets 只包含括号的字符串
	 * @return 如果字符串有效，返回true；否则返回false
	 */
	public static boolean effectiveBrackets(String brackets) {
		Stack<Character> stack = new Stack<>();

		// 遍历字符串中的每个字符
		for (int i = 0; i < brackets.length(); i++) {
			char current = brackets.charAt(i);

			// 遇到开括号 '('，将其压入栈中
			if (current == '(') {
				stack.push(current);
			}
			// 遇到闭括号 ')'，检查栈是否有对应的开括号
			else if (current == ')') {
				// 如果栈为空，说明没有对应的 '('，返回 false
				if (stack.isEmpty()) {
					return false;
				}
				// 弹出栈顶的 '('
				stack.pop();
			}
		}

		// 如果栈为空，说明括号是有效的，返回 true；否则返回 false
		return stack.isEmpty();
	}

	// 算法陷阱
	/**
	 * 忽略边界条件：在设计算法时，如果没有考虑到输入数据的边界情况，可能会导致程序在边界情况下出错。例如，在处理数组索引时，需要确保不会出现数组越界的情况。
	 * 忽略时间复杂度：对于大规模的数据集，时间复杂度高的算法可能会导致超时。选手需要考虑算法的时间复杂度，并在必要时寻求更高效的算法。
	 * 使用不恰当的数据结构：选择合适的数据结构对于算法的效率相关重要，使用不当的数据结构可能会导致算法运行缓慢或者无法正确实现功能。
	 */
	static void trap() {
	}

	// 贪心思维
	/**
	 * 给顶一组硬币面额和总金额，使用最少的硬币凑成这个金额。 {1，5，10，20，50，100}，凑出63元
	 * 贪心会选择一个50元，一个10元三个一元，总共5个硬币，其他选择会选择更多的硬币。
	 */
	static void leastCoin(int amount) {
		int[] coins = { 1, 5, 10, 20, 50, 100 };
		Arrays.sort(coins);
		int count = 0;
		for (int i = coins.length - 1; i >= 0; i--) {
			if (amount >= coins[i]) {
				count += amount / coins[i];
				amount %= coins[i];
			}
		}
		System.out.println("least coins is " + count);
	}
}
